package fireway;

public class HashTable {
    private DataItem[] mHashArray;

    private int mArraySize;

    public HashTable(int size) {
        mArraySize = size;
        mHashArray = new DataItem[mArraySize];
    }

    public void insert(DataItem item) {
        int data = item.getData();
        int indexOfHash = hashFunc(data);

        while (mHashArray[indexOfHash] != null) {
            indexOfHash++;
            indexOfHash %= mArraySize;
        }

        mHashArray[indexOfHash] = item;
    }

    public DataItem delete(int data) {
        int hash = hashFunc(data);

        while (mHashArray[hash] != null) {
            if (data == mHashArray[hash].getData()) {
                DataItem tmp = mHashArray[hash];
                mHashArray[hash] = null;
                return tmp;
            }
            hash++;
            hash %= mArraySize;
        }

        return null;
    }

    /**
     *  哈希函数必须把关键字的范围压缩到数组的范围，这里使用取余操作符来完成
     */
    private int hashFunc(int data) {
        return data % mArraySize;
    }

    public DataItem find(int data) {
        int hash = hashFunc(data);

        while (mHashArray[hash] != null) {
            if (data == mHashArray[hash].getData()) {
                return mHashArray[hash];
            }
            hash++;
            hash %= mArraySize;
        }

        return null;
    }

    public void display() {
        System.out.print("table: ");

        for (int i = 0; i < mArraySize; i++) {
            if (null == mHashArray[i]) {
                System.out.print("^ ");
            } else {
                System.out.print(mHashArray[i].getData() + " ");
            }
        }

        System.out.print("\n");
    }
}

